#include <iostream>
#include <ctime>
#include <random>
using namespace std;

int* partition(int *arr, int *left, int *right)
{
	int Key = *left;
	int *p1 = left;
	int *p2 = right;

	while (p1 < p2)
	{
		while (p1 < p2 && *p2 >= Key)
			--p2;
		while (p1 < p2 && *p1 <= Key)
			++p1;
		if (*p1 != *p2)
			swap(*p1, *p2);
	}
	if (left < right)
		swap(*p1, *left);
	for (int i = 0; i < 7; ++i)
		cout << arr[i] << " ";
	cout << "Key: " << Key << endl;
	return p1;
}
int * Random(int *arr, int *left, int *right)
{
	srand(time(NULL));
	size_t i = rand() % (left - right);
	swap(*left, *(left + i));
	return partition(arr, left, right);
}

int GetIndexNum(int *left, int *right)
{
	return right - left;
}

int* RandomSelect(int *arr, int *left, int *right, int r)
{
	if (left == right)
		return left;

	int *p = Random(arr, left, right);
	int i = GetIndexNum(arr, p);
	if (i == r)
		return p;

	if (i > r)
		return RandomSelect(arr, left, p - 1, r);
	else
		return RandomSelect(arr, p + 1, right, r);
}

int main()
{
 	int arr1[] = {1, 121, 3, 16, 29, 221, 42};
	int *p = RandomSelect(arr1, &arr1[0], &arr1[6],3);
	return 0;
}
